"""

https://www.bilibili.com/video/BV1Ks411575U/?spm_id_from=trigger_reload
"""

tu = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D'],
}


def BFS(graph, s):
    """
    广度优先遍历
    :param graph:
    :param s:
    : return
    """
    queue = []
    visited = set()

    if s not in graph:
        return None

    queue.append(s)
    visited.add(s)
    while len(queue) > 0:
        head = queue.pop(0)
        children = graph[head]
        for child in children:
            if child not in visited:
                queue.append(child)
                visited.add(child)

        print(head)


def DFS(graph, s):
    stack = []
    visited = set()

    stack.append(s)
    visited.add(s)
    while len(stack) > 0:
        top = stack.pop()
        children = graph[top]
        for child in children:
            if child not in visited:
                stack.append(child)
                visited.add(child)
        print(top)


if __name__ == '__main__':
    BFS(tu, 'A')
    DFS(tu, 'A')
